906E - Reverses - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

int n;
char s[1000010],ch1[500010],ch2[500010];

struct palTree{
    int cnt,last,len[1000010],trie[1000010][26],fail[1000010],diff[1000010],slink[1000010];
    palTree()
    {
        cnt=1,len[1]=-1,fail[0]=1,slink[0]=1;
    }
    void ins(int ch,int i,char s[]){
        int p=last;
        while(i-len[p]<=0 || s[i-len[p]-1]!=s[i]) p=fail[p];
        if(!trie[p][s[i]-'a']){
            len[++cnt]=len[p]+2;
            int q=fail[p];
            while(i-len[q]<=0 || s[i-len[q]-1]!=s[i]) q=fail[q];
            fail[cnt]=trie[q][ch];
            trie[p][ch]=cnt;
            diff[cnt]=len[cnt]-len[fail[cnt]];
            slink[cnt]=(diff[cnt]==diff[fail[cnt]]) ? slink[fail[cnt]] : fail[cnt];
        }
        last=trie[p][ch];
    }
}tree;

int dp[1000010],g[1000010],pre[1000010];

int main(){
    scanf("%s%s",ch1+1,ch2+1);
    n=strlen(ch1+1)<<1;
    for(int i=1;i<=n;i++){
        if (i&1) s[i]=ch1[i+1>>1];
        else s[i]=ch2[i>>1];
    }
    for(int i=1;i<=n;i++){
        dp[i]=0x3f3f3f3f;
        tree.ins(s[i]-'a',i,s);
        if(!(i&1) && s[i]==s[i-1] && dp[i-2]<dp[i]){
            dp[i]=dp[i-2],pre[i]=i-2;
        }
        for(int p=tree.last; p; p=tree.slink[p]){
            g[p]=i-tree.len[tree.slink[p]]-tree.diff[p];
            if(tree.slink[p]!=tree.fail[p] && dp[g[p]]>dp[g[tree.fail[p]]]) g[p]=g[tree.fail[p]];
            if(!(i&1) && dp[i]>dp[g[p]]+1) dp[i]=dp[g[p]]+1,pre[i]=g[p];
        }
    }
    if(dp[n]==0x3f3f3f3f){
        puts("-1");return 0;
    }
    printf("%d\n",dp[n]);
    for(int i=n; i>=1; i=pre[i])
        if(i-pre[i]!=2) printf("%d %d\n",(pre[i]>>1)+1,i>>1);
}/*1694671193.5587075*/